Genius42's solve with some tiny optimizations from jammuu (me :D)